/*
 * The class generates new automaton with the given attributes.
 */

package cz.muni.fi.xkadlec6.bp.automaton;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import javax.swing.SwingWorker;

/**
 * The class AutomatonGenerator has the method generateAutomaton(), which creates the instance of the class Automaton
 * with the given attributes
 * 
 * @author Jana Kadlecova
 */
public class AutomatonGenerator
{

	/**
	 * Constructor is private, that make impossible to create the instances
	 */
	private AutomatonGenerator()
	{
	}

	/**
	 * generates the automaton with the given properties.
	 * 
	 * @param numberOfStates_min
	 *            number of states min (>=1)
	 * @param numberOfStates_max
	 *            number of states max
	 * @param numberOfFinalStates_min
	 *            number of final states min (>= 0)
	 * @param numberOfFinalStates_max
	 *            number of final states max
	 * @param numberOfTransitions_min
	 *            number of transitions min (>= 0)
	 * @param numberOfTransitions_max
	 *            number of transitions max
	 * @param alphabetSize_min
	 *            size of alphabet min (>=0)
	 * @param alphabetSize_max
	 *            size of alphabet max
	 * @param unreachableStates_min
	 *            number of unreachable states min (>=0)
	 * @param unreachableStates_max
	 *            number of unreachable states max
	 * @param deterministic
	 * @param totalTransitionFunction
	 * @param hasEpsilonTransitions
	 * @param thread
	 *            thread, which performs this task
	 * @return generated Automaton or null, if the thread is cancelled
	 */
	public static Automaton generateAutomaton(int numberOfStates_min, int numberOfStates_max,
		int numberOfFinalStates_min, int numberOfFinalStates_max, int numberOfTransitions_min,
		int numberOfTransitions_max, int alphabetSize_min, int alphabetSize_max, int unreachableStates_min,
		int unreachableStates_max, boolean deterministic, boolean hasEpsilonTransitions,
		boolean totalTransitionFunction, SwingWorker<Integer, Integer> thread)
	{
		// checking input arguments

		if (unreachableStates_min < 0 || unreachableStates_max < 0)
		{
			throw new IllegalArgumentException("-1");
		}
		if (deterministic
			& totalTransitionFunction
			& ((numberOfTransitions_min > alphabetSize_max * (unreachableStates_max + 1)) || (numberOfTransitions_max < alphabetSize_min
				* (unreachableStates_min + 1))))
		{
			throw new IllegalArgumentException("deterministic & totalTransitionFunction & \n"
				+ "((numberOfTransitions_min> alphabetSize_max * (unreachableStates_max + 1)) ||\n"
				+ " (numberOfTransitions_max < alphabetSize_min * (unreachableStates_min+1) ) )");
		}
		if (deterministic
			& totalTransitionFunction
			& ((numberOfTransitions_min > alphabetSize_max * numberOfStates_max) || (numberOfTransitions_max < alphabetSize_min
				* numberOfStates_min)))
		{
			throw new IllegalArgumentException("deterministic & totalTransitionFunction & \n"
				+ "((numberOfTransitions_min > alphabetSize_max * numberOfStates_max) || \n"
				+ "(numberOfTransitions_max < alphabetSize_min * numberOfStates_min ))");
		}
		if (numberOfStates_min > numberOfStates_max)
		{
			throw new IllegalArgumentException("numberOfStates_min > numberOfStates_max");
		}
		if (numberOfFinalStates_min > numberOfFinalStates_max)
		{
			throw new IllegalArgumentException("numberOfFinalStates_min > numberOfFinalStates_max");
		}
		if (numberOfTransitions_min > numberOfTransitions_max)
		{
			throw new IllegalArgumentException("numberOfTransitions_min > numberOfTransitions_max");
		}
		if (alphabetSize_min > alphabetSize_max)
		{
			throw new IllegalArgumentException("alphabetSize_min > alphabetSize_max");
		}
		if (unreachableStates_min > unreachableStates_max)
		{
			throw new IllegalArgumentException("unreachableStates_min > unreachableStates_max");
		}
		if (deterministic & hasEpsilonTransitions)
		{
			throw new IllegalArgumentException("deterministic & hasEpsilonTransitions");
		}
		if (deterministic & (numberOfTransitions_min > numberOfStates_max * alphabetSize_max))
		{
			throw new IllegalArgumentException(
				"deterministic & (numberOfTransitions_min > numberOfStates_max*alphabetSize_max)");
		}
		if (numberOfFinalStates_min > numberOfStates_max)
		{
			throw new IllegalArgumentException("numberOfFinalStates_min > numberOfStates_max");
		}
		if (alphabetSize_min > numberOfTransitions_max)
		{
			throw new IllegalArgumentException("alphabetSize_min > numberOfTransitions_max");
		}
		if (numberOfTransitions_min > numberOfStates_max * numberOfStates_max
			* (alphabetSize_max + (hasEpsilonTransitions ? 1 : 0)))
		{
			throw new IllegalArgumentException(
				"numberOfTransitions_min > numberOfStates_max*numberOfStates_max*(alphabetSize_max+(hasEpsilonTransitions ? 1 : 0))");
		}
		if (unreachableStates_min > (numberOfStates_max - 1))
		{
			throw new IllegalArgumentException("unreachableStates_min > (numberOfStates_max - 1)");
		}
		if (numberOfTransitions_min > (numberOfStates_max * numberOfStates_max * (alphabetSize_max + (hasEpsilonTransitions ? 1
			: 0)))
			- unreachableStates_max
			* (numberOfStates_max - unreachableStates_max)
			* (alphabetSize_max + (hasEpsilonTransitions ? 1 : 0)))
		{
			throw new IllegalArgumentException(
				"numberOfTransitions_min > (numberOfStates_max*numberOfStates_max*(alphabetSize_max+(hasEpsilonTransitions ? 1 : 0))) - unreachableStates_max * (numberOfStates_max - unreachableStates_max) *(alphabetSize_max+(hasEpsilonTransitions ? 1 : 0))");
		}
		if (numberOfTransitions_max < (numberOfStates_min - unreachableStates_max - 1))
		{
			throw new IllegalArgumentException(
				"numberOfTransitions_min < (numberOfStates_min - unreachableStates_max - 1)");
		}
		if (numberOfStates_min < 0 || numberOfStates_max < 0)
		{
			throw new IllegalArgumentException("numberOfStates_min or numberOfStates_max < 0");
		}
		if (numberOfFinalStates_min < 0 || numberOfFinalStates_max < 0)
		{
			throw new IllegalArgumentException("numberOfFinalStates_min or numberOfFinalStates_max < 0");
		}
		if (alphabetSize_min < 0 || alphabetSize_max < 0)
		{
			throw new IllegalArgumentException("alphabetSize_min or alphabetSize_max < 0");
		}
		if (numberOfTransitions_min < 0 || numberOfTransitions_max < 0)
		{
			throw new IllegalArgumentException("numberOfTransitions_min or numberOfTransitions_max < 0");
		}
		if (thread == null)
		{
			throw new NullPointerException("The thread is null.");
		}

		// setting (randomly) attributes of the generated automaton

		int numberOfStates;
		int numberOfFinalStates;
		int numberOfTransitions;
		int alphabetSize;
		int unreachableStates_count;

		do
		{
			numberOfStates = randomInt(numberOfStates_min, numberOfStates_max);
			alphabetSize = randomInt(alphabetSize_min, alphabetSize_max);
			numberOfFinalStates = randomInt(numberOfFinalStates_min, numberOfFinalStates_max);
			if (totalTransitionFunction & deterministic)
			{
				numberOfTransitions = numberOfStates * alphabetSize;
			}
			else
			{
				numberOfTransitions = randomInt(numberOfTransitions_min, numberOfTransitions_max);
			}
			unreachableStates_count = randomInt(unreachableStates_min, unreachableStates_max);
		}
		while (numberOfFinalStates > numberOfStates
			|| alphabetSize > numberOfTransitions
			|| (numberOfTransitions > numberOfStates * numberOfStates
				* (alphabetSize + (hasEpsilonTransitions ? 1 : 0)))
			|| (numberOfTransitions > (numberOfStates * numberOfStates * (alphabetSize + (hasEpsilonTransitions ? 1 : 0)))
				- unreachableStates_count
				* (numberOfStates - unreachableStates_count)
				* (alphabetSize + (hasEpsilonTransitions ? 1 : 0)))
			|| (numberOfTransitions < (numberOfStates - unreachableStates_count - 1))
			|| (numberOfStates <= unreachableStates_count)
			|| (deterministic & (numberOfTransitions > numberOfStates * alphabetSize)));
		// creating empty Automaton
		Automaton a = new Automaton("s0");
		// adding new states
		for (int i = 1; i <= numberOfStates - 1; i++)
		{
			String stateName = "s" + Integer.valueOf(i).toString();
			a.addState(stateName);
		}
		// generating alphabet
		List<String> alphabet = makeAlphabet(alphabetSize);
		if (hasEpsilonTransitions)
		{
			alphabet.add("epsilon");
		}
		// generating unreachableStates
		Set<String> unreachableStates = new HashSet<String>();
		while (unreachableStates.size() < unreachableStates_count)
		{
			String rs = getRandomElement(a.getStates());
			if (!(unreachableStates.contains(rs)) & !rs.equals(a.getStartState()))
			{
				unreachableStates.add(rs);
			}
		}
		// adding new transfsitions
		while (a.getNumberOfTransitions() < numberOfTransitions)
		{
			// STOP?
			if (thread.isCancelled())
			{
				return null;
			}

			// computing unconnected states (from the perspective of start state)
			Set<String> S0 = new HashSet<String>(); // connected states
			S0.add(a.getStartState()); // the start state is connected
			Set<String> S1 = new HashSet<String>(); // new set of connected states
			while (!S0.equals(S1))
			{
				S1.addAll(S0);
				for (String s : new HashSet<String>(S0))
				{
					try
					{
						S0.addAll(a.getStates(s));
						S0.addAll(getStatesLeadingToState(a, s));
					}
					catch (NoSuchStateException nsse)
					{
						throw new Error(nsse);
					}
				}
			} // S0 = connected states
			Set<String> unconnectedStates = new HashSet<String>(a.getStates());
			unconnectedStates.removeAll(S0);
			String s_from = "";
			String s_to = "";

			if (a.getNumberOfUnreachableStates() > unreachableStates_count)
			{
				Set<String> reachableStates = new HashSet<String>(a.getStates());
				reachableStates.removeAll(unreachableStates);

				S0 = new HashSet<String>(); // reachable states
				S0.add(a.getStartState()); // the start state is reachable
				S1 = new HashSet<String>(); // new set of reachable states
				while (!S0.equals(S1))
				{
					S1.addAll(S0);
					for (String s : new HashSet<String>(S0))
					{
						try
						{
							S0.addAll(a.getStates(s));
						}
						catch (NoSuchStateException nsse)
						{
							throw new Error(nsse);
						}
					}
				}
				// S0 == currenty reachable states
				// CURS = currenty unreachable states
				Set<String> CURS = new HashSet<String>(a.getStates());
				CURS.removeAll(S0);

				Set<String> unwantedURS = new HashSet<String>(CURS);
				unwantedURS.removeAll(unreachableStates);
				s_from = getRandomElement(S0);
				s_to = getRandomElement(unwantedURS);

			}
			else
			{
				if (unconnectedStates.size() > 0)
				{ // a is fully not connected
					if (randomInt(0, 1) == 1)
					{
						s_from = getRandomElement(S0);
						s_to = getRandomElement(unconnectedStates);
					}
					else
					{
						s_from = getRandomElement(unconnectedStates);
						s_to = getRandomElement(S0);
					}
				}
				else
				{
					s_from = getRandomElement(a.getStates());
					s_to = getRandomElement(a.getStates());
				}
			}

			// this is new
			if (unreachableStates.contains(s_to) & !unreachableStates.contains(s_from))
			{
				continue;
			}

			Set<String> currentAlphabet = new HashSet<String>(a.getAlphabet());
			if (a.containsEpsilonTransitions())
			{
				currentAlphabet.add("epsilon");
			}
			Set<String> remainingChars = new HashSet<String>(alphabet);
			remainingChars.removeAll(currentAlphabet);
			Set<String> possibleUnder;
			if (!remainingChars.isEmpty())
			{
				possibleUnder = new HashSet<String>(remainingChars);
			}
			else
			{
				possibleUnder = new HashSet<String>(alphabet);
			}
			for (String c : alphabet)
			{
				try
				{
					// testing wheter the transition (s_from,under,s_to) already exists
					if (a.getStates(s_from, c).contains(s_to))
					{
						possibleUnder.remove(c);
					}
					if ((!(a.getStates(s_from, c).isEmpty())) & deterministic)
					{
						possibleUnder.remove(c);
					}
				}
				catch (NoSuchStateException nsse)
				{
					throw new Error("AutomatonGenerator.generateAutomaton(): " + nsse.getMessage());
				}
			}

			if (possibleUnder.isEmpty())
			{
				continue;
			}

			String under = getRandomElement(possibleUnder);
			try
			{
				a.addTransition(s_from, under, s_to);
			}
			catch (NoSuchStateException nsse)
			{
				throw new Error("AutomatonGenerator.generateAutomaton(): " + nsse.getMessage());
			}

		}
		// adding final states
		while (a.getFinalStates().size() < numberOfFinalStates)
		{
			try
			{
				if (a.getFinalStates().size() == 0)
				{
					Set<String> reachableStates = new HashSet<String>(a.getStates());
					reachableStates.removeAll(unreachableStates);
					a.addToFinalStates(getRandomElement(reachableStates));
				}
				else
				{
					a.addToFinalStates(getRandomElement(a.getStates()));
				}
			}
			catch (NoSuchStateException nsse)
			{
				throw new Error("AutomatonGenerator.generateAutomaton(): " + nsse.getMessage());
			}
		}
		if (deterministic)
		{
			a.setIsNFA(false);
		}
		else
		{
			a.setIsNFA(true);
		}
		return a;
	}

	/**
	 * returns random number from the given interval
	 * 
	 * @param min
	 *            minimal number
	 * @param max
	 *            maxima number
	 * @return random number from the given interval
	 */
	private static int randomInt(int min, int max)
	{
		return (int) Math.floor(Math.random() * (max - min) + min + 0.5);
	}

	/**
	 * makes the alphabet a, b, c...
	 * 
	 * @param count
	 *            number of items
	 * @return alphabet
	 */
	private static List<String> makeAlphabet(int count)
	{
		List<String> alphabet = new ArrayList<String>();
		char c = 'a';
		for (int i = 0; i < count; i++)
		{
			if (i < 26)
			{
				alphabet.add(Character.toString(c));
				c++;
			}
			else
			{
				alphabet.add('z' + Integer.toString(i - 25));
			}
		}
		return alphabet;
	}

	/**
	 * returns the random element in the given collection
	 * 
	 * @param c
	 *            collection
	 * @return random element in the given collection
	 */
	private static String getRandomElement(Collection<String> c)
	{
		return new ArrayList<String>(c).get(randomInt(0, c.size() - 1));
	}

	private static Set<String> getStatesLeadingToState(Automaton a, String state)
	{
		Set<String> alphabet = new HashSet<String>(a.getAlphabet());
		if (a.containsEpsilonTransitions())
		{
			alphabet.add("epsilon");
		}
		Set<String> states = new HashSet<String>();
		try
		{
			for (String s_from : a.getStates())
			{
				for (String under : alphabet)
				{
					if (a.getStates(s_from, under).contains(state))
					{
						states.add(s_from);
					}

				}
			}
		}
		catch (Exception e)
		{
		}
		return Collections.unmodifiableSet(states);
	}

}
